/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/matrix-zigzag-traversal
   @Language: C++
   @Datetime: 17-03-15 08:51
   */

// Method 1
class Solution {
public:
	/**
	 * @param matrix: a matrix of integers
	 * @return: a vector of integers
	 * Tip: when touch the bound, make turn.
	 *      bound : first row/col and last row/col
	 */
	vector<int> printZMatrix(vector<vector<int> > &mat) {
		// write your code here
		vector<int> vs;
		if (mat.size()<1 || mat[0].size()<1) return vs;
		int row=mat.size(), col=mat[0].size(), step=0;
		if (row==1 || col==1){		// single row/col
			for (int i=0; i<row; ++i)
				for (int j=0; j<col; ++j)
					vs.push_back(mat[i][j]);
			return vs;
		}
		for(int i=0, j=0; i<row && j<col; i+=step, j-=step){
			vs.push_back(mat[i][j]);
			if (i==0){
				if (j<col-1) vs.push_back(mat[i][++j]);
				else if (i<row-1) vs.push_back(mat[++i][j]);
				step=1;
			}
			else if (j==0){
				if (i<row-1) vs.push_back(mat[++i][j]);
				else if (j<col-1) vs.push_back(mat[i][++j]);
				step=-1;
			}
			else if (i==row-1){
				if (j<col-1) vs.push_back(mat[i][++j]);
				step=-1;
			}
			else if (j==col-1){
				if (i<row-1) vs.push_back(mat[++i][j]);
				step=1;
			}
		}
		return vs;
	}
};

// Method 2
class Solution{
public:
	/**
	 * @param mat: a matrix of integers
	 * @return: a vector of integers
	 * Tip: Only two line: 1)from right-top to left-bottom
	 *                     2)from left-bottom to right-top
	 * when odd (1,3,...), line 1)
	 * when even(0,2,4..), line 2)
	 */
	vector<int> printZMatrix(vector<vector<int> > &mat){
		if (mat.size()<1 || mat[0].size()<1) return {};
		int row=mat.size(), col=mat[0].size();
		vector<int> vs(row*col,0);
		for (int i=0, k=0; i<row+col-1; ++i){
			if (i&1)	// odd
				for (int j=min(i,col-1), m=max(0,i-row+1); j>=m; --j)
					vs[k++] = mat[i-j][j];
			else		// even
				for (int j=min(i,row-1), m=max(0,i-col+1); j>=m; --j)
					vs[k++] = mat[j][i-j];
		}
		return vs;
	}
}
